package _06_动态规划;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _740_删除并获得点数 {

    public static void main(String[] args) {

        _740_删除并获得点数 v = new _740_删除并获得点数();

        int[] ins = {3};
        System.out.println(v.deleteAndEarn(ins));

    }

    public int deleteAndEarn(int[] nums) {
        // 计算最大值
        int maxValue = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxValue) maxValue = nums[i];
        }
        int[] map = new int[maxValue + 1];
        for (int i : nums) {
            map[i] += i;
        }

        // 打家劫舍动态规划
        int first = 0;
        int second = map[0];
        for (int i = 1; i < map.length; i++) {
            int next = Math.max(map[i] + first, second);
            first = second;
            second = next;
        }
        return second;
    }

    // 排序动态规划
    public int deleteAndEarn2(int[] nums) {
        Arrays.sort(nums);
        int[] map = new int[10001];
        for (int num : nums) {
            map[num]++;
        }
        int begin = map[nums[0]];
        int first = 0;
        int second = nums[0] * map[nums[0]];
        while (begin < nums.length) {
            int count = map[nums[begin]];
            int next;
            if (nums[begin] - nums[begin - 1] == 1) {
                next = Math.max(nums[begin] * count + first, second);
            } else {
                next = second + nums[begin] * count;
            }
            first = second;
            second = next;
            begin += map[nums[begin]];
        }
        return second;
    }

    public int deleteAndEarn1(int[] nums) {
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int begin = map.get(nums[0]);
        int first = 0;
        int second = nums[0] * map.get(nums[0]);
        while (begin < nums.length) {
            int count = map.get(nums[begin]);
            int next;
            if (nums[begin] - nums[begin - 1] == 1) {
                next = Math.max(nums[begin] * count + first, second);
            } else {
                next = second + nums[begin] * count;
            }
            first = second;
            second = next;
            begin += map.get(nums[begin]);
        }
        return second;
    }

}
